#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 589. N 叉树的前序遍历.py
@time: 2022/2/21 15:37
@desc: https://leetcode-cn.com/problems/n-ary-tree-preorder-traversal/
> 给定一个 n叉树的根节点 root，返回 其节点值的 前序遍历 。

n 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。

1. Ot(N), Os(N)

'''
# Definition for a Node.
class Node(object):
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children

class Solution(object):
    def preorder(self, root):
        """
        :type root: Node
        :rtype: List[int]
        """
        if not root: return []
        stack, res = [root], []
        while stack:
            node = stack.pop()
            res.append(node.val)
            while node.children:
                stack.append(node.children.pop())

        return res